package company.tree;

import java.util.Scanner;

/**
 * 450. 删除二叉搜索树中的节点 (递归方式)
 */
public class BinaryTreeDeleteNode {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split("\\s+");
        String[] node = input[0].replace("[", "").
                replace("]", "").replace("\\s+", "").split(",");
        String key = input[1].replace("\\s+", "");
        Tree tree = new Tree();
        tree.root = tree.packTree(tree.root, node);
        deleteNode(tree.root, Integer.parseInt(key));
        System.out.println(tree.levelPrint(tree.root));
    }

    public static TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return root;
        }

        // 从左子树删除
        if (root.getValue() > key) {
            root.setLeft(deleteNode(root.getLeft(), key));
            return root;
        }

        // 从右子树删除
        if (root.getValue() < key) {
            root.setRight(deleteNode(root.getRight(), key));
            return root;
        }

        // 删除操作
        if (root.getValue() == key) {
            // 如果删除的是叶子节点
            if (root.getLeft() == null && root.getRight() == null) {
                return null;
            }

            // 如果删除的节点有一个右节点
            if (root.getLeft() == null) {
                return root.getRight();
            }

            // 如果删除的节点右一个左节点
            if (root.getRight() == null) {
                return root.getLeft();
            }

            // 如果删除的节点右左右节点
            // 找出删除节点的最小右节点
            TreeNode successor = root.getRight();
            while (successor.getLeft() != null) {
                successor = successor.getLeft();
            }

            // 将删除节点设置为右子树的最小的节点 ，同时删掉右子树最小的节点
            root.setRight(deleteNode(root.getRight(), successor.getValue()));
            // 设置删除掉的节点左右节点
            successor.setRight(root.getRight());
            successor.setLeft(root.getLeft());
            return successor;
        }
        return root;
    }
}

